package practice1_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Practice139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[][] res=new boolean[s.length()][s.length()];
        char[] chars=s.toCharArray();
        HashMap<String ,Integer> map=new HashMap<>();
        for(int i=0;i<wordDict.size();i++){map.put(wordDict.get(i),0);}
        for(int i=0;i<s.length();i++){
            for(int j=0;j<=i;j++){
                if(map.containsKey(s.substring(j,i+1))){
                    res[j][i]=true;
                }
                if((j-1>=0)&&map.containsKey(s.substring(0,j))){
                    res[0][j-1]=true;
                }
                if(j-1>=0) res[0][i]=res[0][i]==true?true:res[0][i]||(res[j][i]&&res[0][j-1]);
            }
        }
        return res[0][s.length()-1];
    }

    public static void main(String[] args) {
        ArrayList<String> list=new ArrayList<String>(Arrays.asList(new String[]{"cats", "dog", "sand", "and", "cat"}));
        boolean a=new Practice139().wordBreak("catsandog",list);
    }
}
